from math import inf


class Solution:

    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        mn, ans = inf, ""
        cnt = l = r = 0
        while r < len(s):
            cnt += s[r] == '1'
            while cnt == k:
                if r - l + 1 < mn or r - l + 1 == mn and s[l:r + 1] < ans:
                    mn = r - l + 1
                    ans = s[l:r + 1]
                cnt -= s[l] == '1'
                l += 1
            r += 1
        return ans
s = Solution()
print(s.shortestBeautifulSubstring(s = "100011001", k = 3))